import java.util.Stack;

//有效的括号(力扣20)

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            //为左括号入栈
            if(c=='('||c=='{'||c=='['){
                stack.push(c);
            }
            else{
                //判断是否为空(避免空指针异常)
                if(!stack.empty()){
                    //看是否能抵消
                    char a=stack.peek();
                    if((a=='('&&c==')')||(a=='{'&&c=='}')||(a=='['&&c==']')){
                        stack.pop();
                    }
                    //不能抵消则入栈
                    else{
                        stack.push(c);
                    }
                }
                //栈为空但是没遍历完则入栈
                else{
                    stack.push(c);
                }
            }
        }
        return stack.empty();
    }
}


//逆波兰表达式(力扣150)
import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        //需要注意的是tokens是字符串数组

        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            // 判断是否为操作数
            if (!token.equals("+") && !token.equals("-") && !token.equals("*") && !token.equals("/")) {
                stack.push(Integer.valueOf(token)); // 是操作数，压入栈
            } else {
                // 是操作符，弹出两个操作数
                int r = stack.pop(); // 右操作数
                int l = stack.pop(); // 左操作数
                int result = 0;
                switch (token) {
                    case "+":
                        result = l + r;
                        break;
                    case "-":
                        result = l - r;
                        break;
                    case "*":
                        result = l * r;
                        break;
                    case "/":
                        result = l / r;
                        break;
                }
                stack.push(result); // 将运算结果压入栈
            }
        }
        return stack.pop(); // 栈中最后剩下的即为结果
    }
}



//栈的压入、弹出序列
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        int j=0;
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<pushV.length;i++){
            stack.push(pushV[i]);
            while(j!=popV.length&&!stack.empty()&&popV[j]==stack.peek()){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}



//最小栈(力扣155)
class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(minStack.peek()>=val){
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int ret=stack.pop();
        if(minStack.peek()==ret){
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {

        return minStack.peek();

    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */